package tencent;

import java.util.Arrays;

/**
 * Author:   dengxin
 * Date:     2020/6/13 9:02 上午
 * 生成格雷码
 * 自一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码(Gray Code)
 * 给定整数n，返回n为的格雷码，顺序为从0开始
 * 1的格雷码为0，1
 * 解法：
 * 1.递归
 * 2.格雷码生成规则
 */
@SuppressWarnings("all")
public class qq1 {

    public String[] getGray(int n) {
        if (n==1) {
            return new String[]{"0", "1"};
        }
        String[] last = getGray(n-1);
        String[] result = new String[2*last.length];
        //原数组元素前面加0，填充新数组前半部分
        for (int i=0; i<last.length; i++) {
            result[i] = "0" + last[i];
        }
        //原数组反向，并在反向后的数组前面加1，填充到新数组后半部分
        for (int i=last.length-1; i>=0; i--) {
            result[result.length-i-1] = "1" + last[i];
        }
        return result;
    }
}
